package lc;
import java.util.*;
import org.junit.*;
public class Ex14 {
    class Solution1 {
        public String longestCommonPrefix(String[] strs) {
            TireNode root = new TireNode();
            for (int i = 0; i < strs.length; i++) {
                insert(strs[i], root);
            }
    
            TireNode cur = root;
            StringBuilder sb = new StringBuilder();
            while (cur != null && cur.chs.size() == 1) {
                for (int t: cur.chs) {
                    sb.append((char)(t + 'a'));
                    cur = cur.nexts[t];
                }
            }
            return sb.toString();
        }
    
        public void insert(String s, TireNode root) {
            char[] cs = s.toCharArray();
            TireNode cur = root;
            int idx;
            for (char c : cs) {
                idx = c - 'a';
                if (cur.nexts[idx] == null) {
                    cur.nexts[idx] = new TireNode();
                    cur.chs.add(idx);
                }
                cur.path++;
                cur = cur.nexts[idx];
            }
            cur.isEnd = true;
        }
    
        class TireNode {
            int path;
            // int chs;
            Set<Integer> chs;
            boolean isEnd;
            TireNode[] nexts;
    
            public TireNode() {
                this.isEnd = false;
                this.path = 0;
                this.chs = new HashSet<>();
                this.nexts = new TireNode[26];
            }
        }
    }


    class Solution {
        public String longestCommonPrefix(String[] strs) {
            TireTree root = new TireTree();
            for (String s: strs) {
                root.insert(s);
            }
            int len = strs.length, res = 0;
            Node cur = root.root;
            while (true) {
                if (cur.path < len) break;
                res++;
                char i = 'a';
                for (; i <= 'z'; i++) {
                    if (cur.getNext(i) != null) break;
                }
                cur = cur.getNext(i);
            }
            return res == 0 ? "" : strs[0].substring(0, res);
        }

        class TireTree {
            Node root;
            List<Integer> tmp;

            public TireTree() {
                root = new Node();
            }

            public void insert(String s) {
                // char[] cs = s.toCharArray();
                // for (int i = 0; i )
                Node cur = root, next;
                for (char c: s.toCharArray()) {
                    if ((next = cur.getNext(c)) == null) {
                        next = new Node();
                        cur.setNext(next, c);
                    }
                    cur.path++;
                    cur = next;
                }
                cur.end = true; //当前单词结束
            }
        }

        class Node {
            Node[] nexts;
            boolean end;
            int path;

            public Node() {
                nexts = new Node[26];
                end = false;
                path = 0;
            }

            public Node getNext(char c) {
                return this.nexts[c - 'a'];
            }

            public void setNext(Node node, char c) {
                this.nexts[c - 'a'] = node;
            }
        }
    }
    @Test
    public void test() {
        Solution s = new Solution();
        String[] ss = {"flower","flow","flight"};
        // String[] ss = {"a"};
        System.out.println(s.longestCommonPrefix(ss));
    }
}
